package com.yubest;

import java.util.*;

/**
 * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 输出：[3, 14.5, 11]
 * 解释：
 * 第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
 *  
 *
 * 提示：
 *
 * 节点值的范围在32位有符号整数范围内。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/11 12:07
 */
public class P0637 {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution637 {

    /**
     * 思路：dfs，先计算树的深度，声明一个二维数据，存储每一层的数的和以及数的个数
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        //计算树的深度
        int depth = depth(root);
        //arr[x][0]，第x层所有数的和，arr[x][1]，第x层数的个数
        long[][] arr = new long[depth][2];
        averageOfLevels(root, 0, arr);
        //计算
        List<Double> result = new ArrayList<>();
        for (long[] anArr : arr) {
            result.add((double) anArr[0] / anArr[1]);
        }
        return result;
    }

    /**
     * 思路：bfs，本身是按顶层开始遍历，然后遍历接下来每一层，算法思想正好与题意相符，自顶向下，计算每一层的平均值
     * @param root
     * @return
     */
    public List<Double> averageOfLevelsBFS(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        long total, count;
        while (!queue.isEmpty()) {
            total = 0;
            count = queue.size();
            for (int i = 0; i < count; i++) {
                if (null != queue.peek()) {
                    TreeNode node = queue.poll();
                    total += node.val;
                    if (null != node.left) {
                        queue.offer(node.left);
                    }
                    if (null != node.right) {
                        queue.offer(node.right);
                    }
                }
            }
            result.add((double) total / count);
        }
        return result;
    }

    private void averageOfLevels(TreeNode node, int depth, long[][] arr) {
        if (null == node) {
            return;
        }
        arr[depth][0] += node.val;
        arr[depth][1]++;
        averageOfLevels(node.left, depth + 1, arr);
        averageOfLevels(node.right, depth + 1, arr);
    }

    private int depth(TreeNode root) {
        if (null == root) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

}
